package prim;

public class Main {
    public static void main(String[] args) {
    	//图顶点邻接表编号表示
    	//数组保存图顶点名字
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //图顶点数量
        int vertexs = data.length;
        //maxValue表示两个顶点之前没有边
        int maxValue = Integer.MAX_VALUE;
        //邻接矩阵的关系使用二维数组表示,maxValue表示两个点不联通
        int[][] weight = new int[][]{
                {maxValue, 		  5, 		7, maxValue, maxValue, maxValue, 		2},
                {		5, maxValue, maxValue, 		  9, maxValue, maxValue, 		3},
                {		7, maxValue, maxValue, maxValue, 		8, maxValue, maxValue},
                {maxValue,        9, maxValue, maxValue, maxValue, 		  4, maxValue},
                {maxValue, maxValue, 		8, maxValue, maxValue, 		  5, 		4},
                {maxValue, maxValue, maxValue, 		  4, 		5, maxValue, 		6},
                {		2, 		  3, maxValue, maxValue, 		4, 		  6, maxValue}};
        Graph graph = new Graph(vertexs, data, weight);
        prim(graph, 0);
        prim2(graph, 0);
        prim_cx(graph, 0);
        //打印maxd
        for(int i=0;i<graph.vertexs;i++) {
        	for(int j=0;j<graph.vertexs;j++) {
        		System.out.printf("%5d", maxd[i][j]);
        	}
        	System.out.println();
        }
    }
    
    //次小生成树
    static int MAXN = 100;
    //static int[] dis = new int[MAXN];
    //记录父节点，比如当前节点为x，他的父亲节点为per[x]
    static int[] per = new int[MAXN]; 
    //二维数组maxd[i][j]表示最小生成树中i点到j点的最远距离
    static int[][] maxd = new int[MAXN][MAXN];
    
    public static void prim_cx(Graph graph, int v) {
    	
    	//次小树部分代码
    	for(int i = 0;i < graph.vertexs;i ++){
            //首先父亲节点都是根节点
            //初始化所有节点父节点都是第一个节点
            per[i] = 0;
        }
    	//次小树结束
    	
        //记录临时的节点位置
        int pos = -1;
        
        //记录临时的最小权边值
        int minimum = Integer.MAX_VALUE;
        
    	//标记已访问顶点（相当于点集U）
        int[] visited = new int[graph.vertexs];
        
        //将开始顶点标记已访问
        visited[v] = 1;
        
        //关键部分
        //lowcost数组记录点集U和点集V之间的最小权值边，含顶点信息
        VertexWeight[] lowcost = new VertexWeight[graph.vertexs];
        
        //初始化第一个顶点到其他点的最小权值
        //相当于点集U到其他点（点集V）的最小权值
        for(int i=0;i<graph.vertexs;i++) {
        	lowcost[i] = new VertexWeight(v,i,graph.weight[0][i]);
        }
        
        //枚举n个顶点
        for(int i=0;i<graph.vertexs;i++) {
        	
        	minimum = Integer.MAX_VALUE;
        	VertexWeight vw = null;
        	
        	//此处找点集U到其他点（点集V）的最小权值
        	//从lowcost找最小权对应顶点
        	for(int j=0;j<graph.vertexs;j++) {
        		if( visited[j]==0 && minimum > lowcost[j].weight) {
        			vw = lowcost[j]; //记录带顶点权值边
                    minimum = lowcost[j].weight;
                    pos = j;
                }
        	}
        	
        	//如果min = max_int表示已经不再有点可以加入最小生成树中
        	if (minimum == Integer.MAX_VALUE)    
                break;
        	
        	//pos为这一轮找到的和点集U最近的顶点
        	//将pos顶点标记为已访问
        	visited[pos] = 1;     //加入最小生成树中
        	
        	//次小树部分代码
        	//更新点之间的距离
        	//注意pos点和其父点之间距离唯一
        	maxd[per[pos]][pos] = minimum;
            maxd[pos][per[pos]] = minimum;
            //次小树结束
        	
        	//输出顶点和权值
        	System.out.println("边<" + graph.data[vw.v1] + "," + graph.data[vw.v2] + "> 权值=" + vw.weight);
            //System.out.println("边<" + vw.v1 + "," + vw.v2 + "> 权值=" + vw.weight);
        	
        	//关键步骤，更新可更新边的权值
        	//遍历全部的点
        	for (int j = 0; j < graph.vertexs; ++j) {
        		
        		//次小树部分代码
                //只是更新我们已经遍历过来的节点
        		//点集U中刚加入的点pos和点集U中的其他点
                if(j != pos && visited[j]==1){
                	//更新两点间的最大权值
                    maxd[j][pos] = Math.max(maxd[j][per[pos]],lowcost[pos].weight);
                    maxd[pos][j] = maxd[j][pos]; 
                }
                //次小树结束
        		
        		//找未访问过的点（相当于点集V）
        		//新加入的点pos到未访问过（点集V）如果有权值小于lowcost的则更新lowcost
                if(visited[j]==0 && lowcost[j].weight > graph.weight[pos][j]) {
                	//更新可更新边的权值
                	lowcost[j] = new VertexWeight(pos,j,graph.weight[pos][j]);
                	
                	//次小树部分代码
                	//新引入的点作为更新了边的点的父节点
                	//j表示点集V中边放入了lowcast的点，
                	//这些点的父节点更新为这一轮加入点集U的点pos
                	per[j] = pos;
                	//次小树结束
                }  
            }
        }
    }

    /**
     * @param graph 图
     * @param v     开始顶点
     */
    /*
     * Prim算法求最小生成树的时候和边数无关，和顶点树有关，所以适合求解稠密网的最小生成树。
	   Prim算法的步骤包括：
	   1. 将一个图分为两部分，一部分归为点集U，一部分归为点集V，U的初始集合为{V1}，V的初始集合为{ALL-V1}。
	   2. 针对U开始找U中各节点的所有关联的边的权值最小的那个，然后将关联的节点Vi加入到U中，并且从V中删除（注意不能形成环）。
	   3. 递归执行步骤2，直到V中的集合为空。
       4. U中所有节点构成的树就是最小生成树。
     */
    //记录选中的边和顶点
    public static void prim3(Graph graph, int v) {
        //记录临时的节点位置
        int pos = -1;
        
        //记录临时的最小权边值
        int minimum = Integer.MAX_VALUE;
        
    	//标记已访问顶点（相当于点集U）
        int[] visited = new int[graph.vertexs];
        
        //将开始顶点标记已访问
        visited[v] = 1;
        
        //关键部分
        //lowcost数组记录点集U和点集V之间的最小权值边，含顶点信息
        VertexWeight[] lowcost = new VertexWeight[graph.vertexs];
        
        //初始化第一个顶点到其他点的最小权值
        //相当于点集U到其他点（点集V）的最小权值
        for(int i=0;i<graph.vertexs;i++) {
        	lowcost[i] = new VertexWeight(v,i,graph.weight[0][i]);
        }
        
        //枚举n个顶点
        for(int i=0;i<graph.vertexs;i++) {
        	
        	minimum = Integer.MAX_VALUE;
        	VertexWeight vw = null;
        	
        	//此处找点集U到其他点（点集V）的最小权值
        	//从lowcost找最小权对应顶点
        	for(int j=0;j<graph.vertexs;j++) {
        		if( visited[j]==0 && minimum > lowcost[j].weight) {
        			vw = lowcost[j]; //记录带顶点权值边
                    minimum = lowcost[j].weight;
                    pos = j;
                }
        	}
        	
        	//如果min = max_int表示已经不再有点可以加入最小生成树中
        	if (minimum == Integer.MAX_VALUE)    
                break;
        	
        	//pos为这一轮找到的和点集U最近的顶点
        	//将pos顶点标记为已访问
        	visited[pos] = 1;     //加入最小生成树中
        	
        	//输出顶点和权值
        	System.out.println("边<" + graph.data[vw.v1] + "," + graph.data[vw.v2] + "> 权值=" + vw.weight);
        	
        	//关键步骤，更新可更新边的权值
        	//遍历全部的点
        	for (int j = 0; j < graph.vertexs; ++j) {
        		//找未访问过的点（相当于点集V）
        		//新加入的点pos到未访问过（点集V）如果有权值小于lowcost的则更新lowcost
                if(visited[j]==0 && lowcost[j].weight > graph.weight[pos][j]) 
                	//更新可更新边的权值
                	lowcost[j] = new VertexWeight(pos,j,graph.weight[pos][j]);
            }
        }
    }
    
    //只记录最小生成树权值
    public static void prim2(Graph graph, int v) {
        //记录临时的节点位置
        int pos = -1;
        
        //记录临时的最小权边值
        int minimum = Integer.MAX_VALUE;
        
    	//标记已访问顶点（相当于点集U）
        int[] visited = new int[graph.vertexs];
        
        //将开始顶点标记已访问
        visited[v] = 1;
        
        //关键部分
        //lowcost数组记录点集U和点集V之间的最小权值
        int[] lowcost = new int[graph.vertexs];
        
        //初始化第一个顶点到其他点的最小权值
        //相当于点集U到其他点（点集V）的最小权值
        for(int i=0;i<graph.vertexs;i++) {
        	lowcost[i] = graph.weight[v][i];
        }
        
        //枚举n个顶点
        for(int i=0;i<graph.vertexs;i++) {
        	
        	minimum = Integer.MAX_VALUE;
        	
        	//此处找点集U到其他点（点集V）的最小权值
        	//从lowcost找最小权对应顶点
        	for(int j=0;j<graph.vertexs;j++) {
        		if( visited[j]==0 && minimum > lowcost[j]) {
                    minimum = lowcost[j];
                    pos = j;
                }
        	}
        	
        	//如果min = max_int表示已经不再有点可以加入最小生成树中
        	if (minimum == Integer.MAX_VALUE)    
                break;
        	
        	//pos为这一轮找到的和点集U最近的顶点
        	//将pos顶点标记为已访问
        	visited[pos] = 1;     //加入最小生成树中
        	
        	//输出权值
        	System.out.println("权值=" + minimum);
        	
        	//关键步骤，更新可更新边的权值
        	//遍历全部的点
        	for (int j = 0; j < graph.vertexs; ++j) {
        		//找未访问过的点（相当于点集V）
        		//新加入的点pos到未访问过（点集V）如果有权值小于lowcost的则更新lowcost
                if(visited[j]==0 && lowcost[j] > graph.weight[pos][j]) 
                	//更新可更新边的权值
                	lowcost[j] = graph.weight[pos][j];             
            }
        }
    }
    
    //记录边和顶点，算法好理解，效率偏低
    public static void prim(Graph graph, int v) {
        //标记已访问顶点（相当于点集U）
        int[] visited = new int[graph.vertexs];
        //将开始顶点标记已访问
        visited[v] = 1;
        //h1、h2标记最小的权值weight位置
        int h1 = -1;      
        int h2 = -1;
        //记录最小权值
        int minWeight = Integer.MAX_VALUE;
        //除开始顶点，将其他graph.verrtexs-1个顶点进行选取
        //此循环为prim操作的轮数，轮数为顶点数-1
        for (int k = 1; k < graph.vertexs; k++) {

            //遍历图的所有情况，找到此轮的最小权值连接的顶点
        	//双循环遍历整个邻接表
            for (int i = 0; i < graph.vertexs; i++) {
                for (int j = 0; j < graph.vertexs; j++) {
                    //选取的顶点要求：i是已经选取的的顶点，j是为选取的顶点，找到满足情况的最小权值，记录位置
                    if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
                        minWeight = graph.weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }

            }
            //将此轮选取的最小权值连接的顶点信息输出，名字表示顶点
            System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值=" + minWeight);
            //将此轮选取的最小权值连接的顶点信息输出，编号表示顶点输出
            //System.out.println("边<" + h1 + "," + h2 + "> 权值=" + minWeight);
            //将此轮选取的顶点标记为已访问
            visited[h2] = 1;
            //重新初始化minWeight值
            minWeight = Integer.MAX_VALUE;
        }
    }
}

/**
 * 图类
 */
class Graph {
    int vertexs; //表示顶点个数
    char[] data;//存放顶点数据
    int[][] weight; //使用邻接矩阵存放边

    public Graph(int vertexs, char[] data, int[][] weight) {
        this.vertexs = vertexs;
        this.data = data;
        this.weight = weight;
    }
}

/**
 * 带顶点权值类
 */
class VertexWeight{
	int v1;//第一个顶点
	int v2;//第二个顶点
	int weight;//两点间的权值
	public VertexWeight(int v1 , int v2, int weight) {
		this.v1 = v1;
		this.v2 = v2;
		this.weight = weight;
	}
}

 